import java.util.Arrays;

public class Optimal {
    public static final int N = 3; // 内存帧数
    private final Object[] array = new Object[N];
    private int size; // 当前帧的数量
    private final int[] longest = new int[N];

    public Optimal() {
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isOutOfBoundary() {
        return size >= N;
    }

    public int indexOfElement(Object o) {
        for (int i = 0; i < size; i++) {
            if (array[i] == o) {
                return i;
            }
        }
        return -1;
    }

    private int findTransIndex(int currentStep, Object[] procList) {
        Arrays.fill(longest, Integer.MAX_VALUE);
        int farthest = -1;
        int transIndex = -1;

        // 查找最远的下次访问索引
        for (int i = 0; i < size; i++) {
            for (int j = currentStep + 1; j < procList.length; j++) {
                if (procList[j] == array[i]) {
                    longest[i] = j;
                    break;
                }
            }
            if (longest[i] > farthest) {
                farthest = longest[i];
                transIndex = i;
            }
        }

        // 找到未被访问的帧
        for (int i = 0; i < size; i++) {
            if (longest[i] == Integer.MAX_VALUE) {
                return i;
            }
        }

        return transIndex;
    }

    public Object push(Object[] procList, int currentStep) {
        Object currentPage = procList[currentStep];
        int pageIndex = indexOfElement(currentPage);

        if (!isOutOfBoundary() && pageIndex == -1) { // 当前帧未满，且页面不在内存中
            array[size++] = currentPage;
            return null;
        } else if (pageIndex != -1) { // 页面已经在内存中
            return array[pageIndex];
        } else if (isOutOfBoundary() && pageIndex == -1) { // 当前帧已满，且页面不在内存中
            int transIndex = findTransIndex(currentStep, procList);
            Object replaced = array[transIndex];
            array[transIndex] = currentPage;
            return replaced;
        }

        return null;
    }

    public Object[] getArray() {
        return array.clone();
    }
}
